package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [1615. 最大网络秩 - 力扣（LeetCode）](https://leetcode.cn/problems/maximal-network-rank/)
 * @since Created by work on 2023/3/15 22:30
 */
public class MaximalNetworkRank {

    public int maximalNetworkRank(int n, int[][] roads) {

        int len = roads.length;
        if (len == 0) {
            return 0;
        }
        Map<Integer, List<Integer>> nodeToLinkNodesMap = new HashMap<>(16);
        List<Integer> preNodes;
        List<Integer> postNodes;
        int firstMaxNodeNum = 0;
        int firstMaxNodeNumIndex = -1;
        int secondMaxNodeNum = 0;
        int preNodeSize;
        int postNodeSize;

        for (int i = 0; i < len; i++) {
            preNodes = nodeToLinkNodesMap.getOrDefault(roads[i][0], new ArrayList<>());
            preNodes.add(roads[i][1]);
            nodeToLinkNodesMap.put(roads[i][0], preNodes);

            preNodeSize = preNodes.size();
            if (preNodeSize > firstMaxNodeNum) {
                if (firstMaxNodeNumIndex != roads[i][0]) {
                    secondMaxNodeNum = firstMaxNodeNum;
                }
                firstMaxNodeNumIndex = roads[i][0];
                firstMaxNodeNum = preNodeSize;
            } else if (preNodeSize > secondMaxNodeNum) {
                secondMaxNodeNum = preNodeSize;
            }

            postNodes = nodeToLinkNodesMap.getOrDefault(roads[i][1], new ArrayList<>());
            postNodes.add(roads[i][0]);
            nodeToLinkNodesMap.put(roads[i][1], postNodes);

            postNodeSize = postNodes.size();
            if (postNodeSize > firstMaxNodeNum) {
                if (firstMaxNodeNumIndex != roads[i][1]) {
                    secondMaxNodeNum = firstMaxNodeNum;
                }
                firstMaxNodeNumIndex = roads[i][1];
                firstMaxNodeNum = postNodeSize;
            } else if (postNodeSize > secondMaxNodeNum) {
                secondMaxNodeNum = postNodeSize;
            }
        }


        List<Integer> firstMaxIndexList = new ArrayList<>();
        List<Integer> secondMaxIndexList = new ArrayList<>();

        Set<Map.Entry<Integer, List<Integer>>> entries = nodeToLinkNodesMap.entrySet();
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            System.out.println(entry.getValue().size());

            if (entry.getValue().size() == firstMaxNodeNum) {
                firstMaxIndexList.add(entry.getKey());
            } else if (entry.getValue().size() == secondMaxNodeNum) {
                secondMaxIndexList.add(entry.getKey());
            }
        }

        System.out.println(firstMaxNodeNum + "-" + firstMaxIndexList.size() + " " + secondMaxNodeNum + "-" + secondMaxIndexList.size());

        if (firstMaxNodeNum == secondMaxNodeNum) {
            int firstMaxIndexListSize = firstMaxIndexList.size();
            for (int i = 0; i < firstMaxIndexListSize - 1; i++) {
                for (int j = i+1; j < firstMaxIndexListSize; j++) {
                    if (!nodeToLinkNodesMap.get(firstMaxIndexList.get(i)).contains(firstMaxIndexList.get(j))) {
                        return firstMaxNodeNum + secondMaxNodeNum;
                    }
                }
            }
//            for (Integer firstMaxIndex : firstMaxIndexList) {
//
//
//                if (!intersection(nodeToLinkNodesMap.get(firstMaxIndex), firstMaxIndexList)) {
//                    return firstMaxNodeNum + secondMaxNodeNum;
//                }
//            }
            return firstMaxNodeNum + secondMaxNodeNum - 1;
        } else {
            for (Integer secondMaxIndex : secondMaxIndexList) {

                if (!nodeToLinkNodesMap.get(secondMaxIndex).contains(firstMaxIndexList.get(0))) {
                    return firstMaxNodeNum + secondMaxNodeNum;
                }
            }
            return firstMaxNodeNum + secondMaxNodeNum - 1;
        }

    }

    private boolean intersection(List<Integer> listA, List<Integer> listB) {

        for (Integer a : listA) {
            for (Integer b : listB) {
                if (Objects.equals(a, b)) {
                    return true;
                }
            }
        }

        return false;
    }
}
